//  Copyright (c) 2014 www.9miao.com All rights reserved.
package dGame3D 
{
	import flash.geom.Point;
	/**
	 * ...
	 * @author ...
	 */
	public class dSearchPath 
	{
		//横或竖向移动一格的路径评分
		private const COST_STRAIGHT : int = 10;
		//斜向移动一格的路径评分
		private const COST_DIAGONAL : int = 14;
		
		//(单个)节点数组 节点ID 索引
		private const NOTE_ID : int = 0;
		//(单个)节点数组 是否在开启列表中 索引
		private const NOTE_OPEN : int = 1;
		//(单个)节点数组 是否在关闭列表中 索引
		private const NOTE_CLOSED : int = 2;
		//====================================
		//	Member Variables
		//====================================
		//最大寻路步数，限制超时返回
		private var m_maxTry : int = 500000;
		
		//开放列表，存放节点ID
		private var m_openList : Array;
		//开放列表长度
		private var m_openCount : int;
		//节点加入开放列表时分配的唯一ID(从0开始)
		//根据此ID(从下面的列表中)存取节点数据
		private var m_openId : int;
		
		//节点x坐标列表
		private var m_xList : Array;
		//节点y坐标列表
		private var m_yList : Array;
		//节点路径评分列表
		private var m_pathScoreList : Array;
		//(从起点移动到)节点的移动耗费列表
		private var m_movementCostList : Array;
		//节点的父节点(ID)列表
		private var m_fatherList : Array;
		
		//节点(数组)地图,根据节点坐标记录节点开启关闭状态和ID
		private var m_noteMap : Array;

		public function dSearchPath() 
		{
			
		}

		/**
		 * 最大寻路步数，限制超时返回
		 */		
		public function get maxTry() : int
		{
			return this.m_maxTry;
		}
		/**
		 * @private
		 */		
		public function set maxTry(p_value : int) : void
		{
			this.m_maxTry = p_value;
		}

		/**
		 * 提供可遍历的节点
		 * 
		 * 这里提供的是八方向移动
		 * 
		 * @param p	当前节点
		 * @return 
		 * 
		 */
		public function getArounds( p:Point ):Array
		{
			return new Array();
		}
		/**
		 * 开始寻路
		 */		
		private function find(start:Point,end:Point,GetCanReach:Function ) : Array
		{
			var p_startX : int = start.x;
			var p_startY : int = start.y;
			var p_endX : int = end.x;
			var p_endY : int = end.y; 
			
			this.initLists();
			this.m_openCount = 0;
			this.m_openId = -1;
			
			this.openNote(p_startX, p_startY, 0, 0, 0);
			
			var currTry : int = 0;
			var currId : int;
			var currNoteX : int;
			var currNoteY : int;
			var aroundNotes : Array;
			
			var checkingId : int;
			
			var cost : int;
			var score : int;
			while (this.m_openCount > 0)
			{
				//超时返回
				if (++currTry > this.m_maxTry)
				{
					this.destroyLists();
					return null;
				}
				//每次取出开放列表最前面的ID
				currId = this.m_openList[0];
				//将编码为此ID的元素列入关闭列表
				this.closeNote(currId);
				currNoteX = this.m_xList[currId];
				currNoteY = this.m_yList[currId];
				
				//如果终点被放入关闭列表寻路结束，返回路径
				if (currNoteX == p_endX && currNoteY == p_endY)
				{
					return this.getPath(p_startX, p_startY, currId);
				}
				//获取周围节点，排除不可通过和已在关闭列表中的
				//aroundNotes = getArounds(new Point(currNoteX, currNoteY));
				aroundNotes = _SearchPathGetAround( currNoteX, currNoteY , GetCanReach );
				//对于周围的每一个节点
				for each (var note : Point in aroundNotes)
				{
					if (isClosed(note.x,note.y))
						continue;
						
					//计算F和G值
					cost = this.m_movementCostList[currId] + ((note.x == currNoteX || note.y == currNoteY) ? COST_STRAIGHT : COST_DIAGONAL);
					score = cost + (Math.abs(p_endX - note.x) + Math.abs(p_endY - note.y)) * COST_STRAIGHT;
					if (this.isOpen(note.x, note.y)) //如果节点已在播放列表中
					{
						checkingId = this.m_noteMap[note.y][note.x][NOTE_ID];
						//如果新的G值比节点原来的G值小,修改F,G值，换父节点
						if(cost < this.m_movementCostList[checkingId])
						{
							this.m_movementCostList[checkingId] = cost;
							this.m_pathScoreList[checkingId] = score;
							this.m_fatherList[checkingId] = currId;
							this.aheadNote(this.getIndex(checkingId));
						}
					} else //如果节点不在开放列表中
					{
						//将节点放入开放列表
						this.openNote(note.x, note.y, score, cost, currId);
					}
				}
			}
			//开放列表已空，找不到路径
			this.destroyLists();
			return null;
		}

		/**
		 * @private
		 * 将节点加入开放列表
		 * 
		 * @param p_x		节点在地图中的x坐标
		 * @param p_y		节点在地图中的y坐标
		 * @param P_score	节点的路径评分
		 * @param p_cost	起始点到节点的移动成本
		 * @param p_fatherId	父节点
		 */
		private function openNote(p_x : int, p_y : int, p_score : int, p_cost : int, p_fatherId : int) : void
		{
			this.m_openCount++;
			this.m_openId++;
			
			if (this.m_noteMap[p_y] == null)
			{
				this.m_noteMap[p_y] = [];
			}
			this.m_noteMap[p_y][p_x] = [];
			this.m_noteMap[p_y][p_x][NOTE_OPEN] = true;
			this.m_noteMap[p_y][p_x][NOTE_ID] = this.m_openId;
			
			this.m_xList.push(p_x);
			this.m_yList.push(p_y);
			this.m_pathScoreList.push(p_score);
			this.m_movementCostList.push(p_cost);
			this.m_fatherList.push(p_fatherId);
			
			this.m_openList.push(this.m_openId);
			this.aheadNote(this.m_openCount);
		}
		/**
		 * @private
		 * 将节点加入关闭列表
		 */
		private function closeNote(p_id: int) : void
		{
			this.m_openCount--;
			var noteX : int = this.m_xList[p_id];
			var noteY : int = this.m_yList[p_id];
			this.m_noteMap[noteY][noteX][NOTE_OPEN] = false;
			this.m_noteMap[noteY][noteX][NOTE_CLOSED] = true;
			
			if (this.m_openCount <= 0)
			{
				this.m_openCount = 0;
				this.m_openList = [];
				return;
			}
			this.m_openList[0] = this.m_openList.pop();
			this.backNote();
		}
		/**
		 * @private
		 * 将(新加入开放别表或修改了路径评分的)节点向前移动
		 */
		private function aheadNote(p_index : int) : void
		{
			var father : int;
			var change : int;
			while(p_index > 1)
			{
				//父节点的位置
				father = Math.floor(p_index / 2);
				//如果该节点的F值小于父节点的F值则和父节点交换
				if (this.getScore(p_index) < this.getScore(father))
				{
					change = this.m_openList[p_index - 1];
					this.m_openList[p_index - 1] = this.m_openList[father - 1];
					this.m_openList[father - 1] = change;
					p_index = father;
				} else
				{
					break;
				}
			}
		}
		/**
		 * @private
		 * 将(取出开启列表中路径评分最低的节点后从队尾移到最前的)节点向后移动
		 */
		private function backNote() : void
		{
			//尾部的节点被移到最前面
			var checkIndex : int = 1;
			var tmp : int;
			var change : int;
			
			while(true)
			{
				tmp = checkIndex;
				//如果有子节点
				if (2 * tmp <= this.m_openCount)
				{
					//如果子节点的F值更小
					if(this.getScore(checkIndex) > this.getScore(2 * tmp))
					{
						//记节点的新位置为子节点位置
						checkIndex = 2 * tmp;
					}
					//如果有两个子节点
					if (2 * tmp + 1 <= this.m_openCount)
					{
						//如果第二个子节点F值更小
						if(this.getScore(checkIndex) > this.getScore(2 * tmp + 1))
						{
							//更新节点新位置为第二个子节点位置
							checkIndex = 2 * tmp + 1;
						}
					}
				}
				//如果节点位置没有更新结束排序
				if (tmp == checkIndex)
				{
					break;
				} 
				//反之和新位置交换，继续和新位置的子节点比较F值
				else
				{
					change = this.m_openList[tmp - 1];
					this.m_openList[tmp - 1] = this.m_openList[checkIndex - 1];
					this.m_openList[checkIndex - 1] = change;
				}
			}
		}
		/**
		 * @private
		 * 判断某节点是否在开放列表
		 */		
		private function isOpen(p_x : int, p_y : int) : Boolean
		{
			if (this.m_noteMap[p_y] == null) return false;
			if (this.m_noteMap[p_y][p_x] == null) return false;
			return this.m_noteMap[p_y][p_x][NOTE_OPEN];
		}
		/**
		 * @private
		 * 判断某节点是否在关闭列表中
		 */		
		private function isClosed(p_x : int, p_y : int) : Boolean
		{
			if (this.m_noteMap[p_y] == null) return false;
			if (this.m_noteMap[p_y][p_x] == null) return false;
			return this.m_noteMap[p_y][p_x][NOTE_CLOSED];
		}

		/**
		 * @private
		 * 获取路径
		 * 
		 * @param p_startX	起始点X坐标
		 * @param p_startY	起始点Y坐标
		 * @param p_id		终点的ID
		 * 
		 * @return 			路径坐标(Point)数组
		 */		
		private function getPath(p_startX : int, p_startY : int, p_id: int) : Array
		{
			var arr : Array = [];
			var noteX : int = this.m_xList[p_id];
			var noteY : int = this.m_yList[p_id];
			while (noteX != p_startX || noteY != p_startY)
			{
				arr.unshift(new Point(noteX, noteY));
				p_id = this.m_fatherList[p_id];
				noteX = this.m_xList[p_id];
				noteY = this.m_yList[p_id];
			}
			arr.unshift(new Point(p_startX, p_startY));
			this.destroyLists();
			return arr;
		}
		/**
		 * @private
		 * 获取某ID节点在开放列表中的索引(从1开始)
		 */		
		private function getIndex(p_id : int) : int
		{
			var i : int = 1;
			for each (var id : int in this.m_openList)
			{
				if (id == p_id)
				{
					return i;
				}
				i++;
			}
			return -1;
		}
		/**
		 * @private
		 * 获取某节点的路径评分
		 * 
		 * @param p_index	节点在开启列表中的索引(从1开始)
		 */		
		private function getScore(p_index : int) : int
		{
			return this.m_pathScoreList[this.m_openList[p_index - 1]];
		}
		/**
		 * @private
		 * 初始化数组
		 */		
		private function initLists() : void
		{
			this.m_openList = [];
			this.m_xList = [];
			this.m_yList = [];
			this.m_pathScoreList = [];
			this.m_movementCostList = [];
			this.m_fatherList = [];
			this.m_noteMap = [];
		}
		/**
		 * @private
		 * 销毁数组
		 */		
		private function destroyLists() : void
		{
			this.m_openList = null;
			this.m_xList = null;
			this.m_yList = null;
			this.m_pathScoreList = null;
			this.m_movementCostList = null;
			this.m_fatherList = null;
			this.m_noteMap = null;
		}
		
		private function _SearchPathGetAround( x:int , z:int , GetCanReach:Function ):Array
		{
			var arr:Array = new Array();
			var bCanRight:Boolean = GetCanReach( x + 1 , z ) == 0;
			var bCanDown:Boolean = GetCanReach( x , z + 1 ) == 0;
			var bCanLeft:Boolean = GetCanReach( x - 1 , z ) == 0;
			var bCanUp:Boolean = GetCanReach( x , z - 1 ) == 0;
			//右
			if( bCanRight )
				arr.push( new Point( x + 1 , z ) );
			//下
			if ( bCanDown )
				arr.push( new Point( x , z + 1 ) );
			//左
			if ( bCanLeft )
				arr.push( new Point( x - 1 , z ) );
			//上
			if ( bCanUp )
				arr.push( new Point( x , z - 1 ) );
			//右下
			if ( GetCanReach( x + 1 , z + 1 ) == 0 && bCanRight && bCanDown )
				arr.push( new Point( x + 1 , z + 1 ) );
			//左下
			if ( GetCanReach( x - 1 , z + 1 ) == 0 && bCanLeft && bCanDown )
				arr.push( new Point( x - 1 , z + 1 ) );
			//左上
			if ( GetCanReach( x - 1 , z - 1 ) == 0 && bCanLeft && bCanUp )
				arr.push( new Point( x - 1 , z - 1 ) );
			//右上
			if ( GetCanReach( x + 1 , z - 1 ) == 0 && bCanRight && bCanUp )
				arr.push( new Point( x + 1 , z - 1 ) );
			return arr;
		}
		public function findPath( GetCanReach:Function , start:Point, end:Point, target:Number=0, deal:Boolean = true, direct:Boolean = true):Array
		{
			var arr:Array = null;
			while (direct)
			{
				var dirX:Number = end.x - start.x;
				var dirY:Number = end.y - start.y;
				var length:Number = Math.sqrt( dirX * dirX + dirY * dirY ) * 0.99;
				if ( length != 0.0 )
				{
					dirX /= length;
					dirY /= length;
				}
				var x:Number = start.x;
				var y:Number = start.y;
				while ( 1 )
				{
					if ( Math.sqrt( (end.x - x)*(end.x - x) + (end.y - y)*(end.y - y) ) <= 1.0 )
					{
						arr = new Array();
						arr.push( end );
						return arr;
					}
					x += dirX;
					y += dirY;
					if ( GetCanReach( x , y ) != 0 ||
						 GetCanReach( x + 1 , y ) != 0 ||
						 GetCanReach( x - 1 , y ) != 0 ||
						 GetCanReach( x , y - 1 ) != 0 ||
						 GetCanReach( x , y + 1 ) != 0 )
						break;
				}
				break;
			}
			
			//A*寻路
			arr = this.find(start, end,GetCanReach);
			
			//路径不存在
			if (!arr || arr.length == 0)
				return arr;
			
			//寻路距离处理
			arr.shift();
			while (arr.length >= 2)
			{
				var top:Object = arr[arr.length-1];
				var top1:Object = arr[arr.length-2];
				target -= Math.sqrt((top.x - top1.x) * (top.x - top1.x) + (top.y - top1.y) * (top.y - top1.y));
				if (target > 0)
					arr.pop();
				else
					break;
			}
			
			//是否需要优化处理
			if (!arr || arr.length == 0)
				return arr;
			if (!deal)
				return arr;

			var result:Array = new Array();
			var v:Object = null;
			var p:Point = null;
			
			//去除直线的冗余点
			for (var i:int = 0; i < arr.length; i++)
			{
				//delete arr[i]["length"];
				if (v == null)
				{
					result.push(arr[i]);
					v = arr[i] as Object;
				}
				else
				{
					if (p == null)
					{
						result.push(arr[i]);
						p = new Point();
						p.x = arr[i]["x"] - v["x"];
						p.y = arr[i]["y"] - v["y"];
						v = arr[i] as Object;
					}
					else
					{
						if (((Math.abs(arr[i]["x"] - v["x"]) < 0.01) && Math.abs(p.x) < 0.01) ||
							((Math.abs(arr[i]["y"] - v["y"]) < 0.01) && Math.abs(p.y) < 0.01) ||
							(Math.abs((arr[i]["x"] - v["x"]) / (arr[i]["y"] - v["y"]) - p.x / p.y)) < 0.01)
						{
							result.pop();
							result.push(arr[i]);
							v = arr[i] as Object;
						}
						else
						{
							result.push(arr[i]);
							p.x = arr[i]["x"] - v["x"];
							p.y = arr[i]["y"] - v["y"];
							v = arr[i] as Object;
						}
					}
				}
			}
			
			//防止锯齿形抖动
			arr = [];
			v = null;
			var canpop:Boolean = false;		// 路径中的某些点不能pop出去
			for (var j:int = 0; j < result.length; j++)
			{
				if (v == null)
				{
					arr.push({x:result[j]["x"],y:result[j]["y"]});
					v = result[j] as Object;
					canpop = false;			// 第一个点不能pop
				}
				else
				{
					if (Math.abs(result[j]["x"] - v["x"]) <= 1.0 && Math.abs(result[j]["y"] - v["y"]) <= 1.0)
					{
						if (canpop)	arr.pop();
						arr.push({x:result[j]["x"],y:result[j]["y"]});
						v = result[j] as Object;
						canpop = true;		// 中间的点可以pop
					}
					else
					{
						arr.push({x:result[j]["x"],y:result[j]["y"]});
						v = result[j] as Object;
						canpop = false;		// 转折点不能pop
					}
				}
			}
			
			return arr;
		}
	}

}